#include<vector>
#include<queue>
using namespace std;

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;

         queue<TreeNode*> q;
         q.push(root);
         int level = 0;
         while (!q.empty())
         {
             int size = q.size();
             vector<int> level_res;
             for(int i = 0; i<size; i++){
                 TreeNode* curr = q.front();
                 q.pop();
                 level_res.push_back(curr->val);
                 if(curr->left) q.push(curr->left);
                 if(curr->right)q.push(curr->right);
             }
             if(level %2==1){
             reverse(level_res.begin(), level_res.end());
         }
         level++;
         res.push_back(level_res);
         }

         return res; 
    }
};